package com.base.greedy;

import java.util.Random;

/**
 * 45. 跳跃游戏 II
 *给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 假设你总是可以到达数组的最后一个位置。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年11月26日 13:46
 */
public class Jump2 {
    public int jump(int[] nums) {

        int n = nums.length-1;
        if(n==0){
            return n;
        }
        int start = 0;
        int step = nums[0];
        int size = 0;
        while(start+step<n){
            /**
             * 如果step为表示不能跳到最后一截阶梯去
             */
            if(step==0){
                return 0;
            }
            int max = 0;
            int index = start;
            /**
             * 找到当前可以到达所有结点中，收益最大的结点, (也就是该结点位置+结点步长)最大
             */
            for( int i = 1;i<=step;i++){
                if(i+nums[start+i]>max){
                    index = start+i;
                    max = i+nums[start+i];
                }

            }
            size++;
            start = index;
            step = nums[start];
        }
        return size+1;
    }

    public int jump1(int[] nums){
        int n = nums.length-1;
        int steps = 0;
        int end = 0;
        int rightMax = 0;
        for (int i = 0; i < n; i++) {
            rightMax = Math.max(rightMax,i+nums[i]);
            if (i==end){
                /**
                 * rightMax==end，表示不能到达下一个结点
                 */
                if(rightMax==end){
                    return 0;
                }
                end = rightMax;
                steps++;


            }
        }
        return steps;
    }
}
